package xu.linkedlist.solution;

public class Solution148 {
    /*
     * 排序链表
     *
     * 这里要求时间复杂度为 O(logN)，空间复杂度为 O(1)，可以想到的是归并排序，而又因为空间复杂度为常数复杂度，
     * 因此不能够使用递归，因此使用自底向上的归并排序算法。下面以 8,5,12,4 这个例子进行讲解：
     *
     * 当 inv = 1 时，将这个长度为 4 的链表拆分成 4 个长度为 1 的子链表，然后再将这 4 个子链表两两合并，即
     * 拆分成 8,5,12,4 这四个子链表，8 和 5 进行合并得到 5,8，12 和 4 进行合并得到 4,12，最后得到的结果为 5,8,4,12
     * 当 inv = 2 时，将这个长度为 4 的链表拆分成 2 个长度为 2 的子链表，然后再将这 2 个子链表两两合并，即
     * 拆分成 5,8 和 4,12 两个链表，然后将其进行合并，得到 4,5,8,12
     *
     * 对于更长的链表，inv 会以 1,2,4,8,16,... 序列进行增长，直到等于或者大于链表的长度
     */
}
